题解 P3449 【[POI2006]PAL-Palindromes】

发表于 | 更新于

题意：给出$n$个回文串$s_1, s_2, \cdots,s_n$求如下二元组$(i, j)$的个数$s_i + s_j$仍然是回文串

对于每个字符串进行$hash$,判断连接形成回文串只需判断$a+b$是否$=$$b+a$即可

注:这里的$x+y$指的是将字符串$y$连到字符串$x$后面去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define N 2000002
#define hash HASH
#define mod 1000000007
#define base 131
using namespace std;
int n,m,hash[N],len[N],ch[N][26],tot,po[N],w[N],ans;
string s[N];
int calc(string s){
    int res=0,len=s.length();
    for (int i=0;i<len;++i)res=(res*base+s[i]-'a')%mod;
    return res;
}
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
void build(string s,int id){
    int len=s.length(),now=0;
    for (int i=0;i<len;++i){
        int v=s[i]-'a';
        if (!ch[now][v])ch[now][v]=++tot;
        now=ch[now][v];
    }
    w[now]=id;
}
void query(string ss,int id){
    int le=ss.length(),now=0;
    for (int i=0;i<le;++i){
        int v=ss[i]-'a';
        now=ch[now][v];
        if (w[now]&&w[now]!=id){
            if ((hash[w[now]]*po[len[id]]%mod+hash[id])%mod==(hash[id]*po[len[w[now]]]%mod+hash[w[now]])%mod){
                ++ans;
            }
        }
    }
}
signed main(){
    n=read();po[0]=1;
    for (int i=1;i<=200000;++i)po[i]=po[i-1]*base%mod;
    for (int i=1;i<=n;++i){
        len[i]=read();cin>>s[i];
        build(s[i],i);
        hash[i]=calc(s[i]);
    }
    for (int i=1;i<=n;++i)
        query(s[i],i);
    cout<<ans*2+n;    
    return 0;
}